import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left; //左孩子
        public TreeNode right; //右孩子
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        B.left = D;
        B.right = E;
        E.right = H;
        A.right = C;
        C.left = F;
        C.right = G;

        return A; //A是根节点
    }

    public void preOrder(TreeNode root){
        //根 左 右
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        //左 根 右
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public void postOrder(TreeNode root){
        //左 右 根
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    public int size1(TreeNode root){
        //左孩子 + 右孩子 + 1（根）
        if(root == null){
            return 0;
        }
        return size1(root.left) + size1(root.right) + 1;
    }

    public int sizeCount = 0;
    public int size2(TreeNode root){
        //通过前中后序遍历，运用计数器
        if(root == null){
            return 0;
        }
        //通过前序遍历
        sizeCount++;
        size2(root.left);
        size2(root.right);

        return sizeCount;
    }

    public int getLeafCount1(TreeNode root){
        //左叶子 + 右叶子
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafCount1(root.left) + getLeafCount1(root.right);
    }

    public int leafCount = 0;
    public int getLeafCount2(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            leafCount++;
            return 0; // 可要可不要，如果加上，缩减了最后叶子节点孩子为空的判断
        }
        getLeafCount2(root.left);
        getLeafCount2(root.right);
        return leafCount;
    }

    /**
     * 求二叉树的第k层有多少个节点
     * @param root 根
     * @param k 层
     * @return int
     */
    public int getKLevelCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            //已经判断完了root不可能为空
            return 1;
        }
        return getKLevelCount(root.left,k-1) +
         getKLevelCount(root.right,k-1);
    }

    /**
     * 求二叉树的深度  左子树的深度 + 右子树的深度 + 1 (根)
     * @param root 根
     * @return int
     */
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftNum = getHeight(root.left);
        int rightNum = getHeight(root.right);

        return Math.max(leftNum,rightNum) + 1;
    }

    /**
     * 找到val所在的节点
     * @param root 根
     * @param val 要找的值
     * @return TreeNode
     */
    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret = find(root.left,val);
        if( ret != null){
            return ret;
        }
        ret = find(root.right,val);
        if( ret != null){
            return ret;
        }
        return null;
    }

    /**
     * 判断两棵树是不是相同的
     * @param p 第一颗树
     * @param q 第二棵树
     * @return boolean
     */
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p == null & q != null || p != null && q == null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        //p q 一定不是null
        if(p.val != q.val){
            return false;
        }
        //此时的根节点已经是相同的了，接着继续判断左孩子和右孩子是否相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    /**
     * 判断subRoot是否是root的子树
     * @param root 根
     * @param subRoot 子树
     * @return boolean
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    /**
     * 反转整颗二叉树
     * @param root 根
     * @return TreeNode根节点
     */
    public TreeNode invertTree(TreeNode root){
        if(root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    /**
     * 判断二叉树是否是轴对称
     * @param root 根
     * @return boolean
     */
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode rootLeft,TreeNode rootRight){
        if(rootLeft!=null&&rootRight==null || rootLeft==null&&rootRight!=null){
            return false;
        }
        if(rootLeft == null && rootRight == null){
            return true;
        }
        if(rootLeft.val != rootRight.val){
            return false;
        }
        return isSymmetricChild(rootLeft.left,rootRight.right) &&
                isSymmetricChild(rootLeft.right,rootRight.left);

    }

    /**
     * 判断二叉树是否平衡
     * @param root 根
     * @return boolean
     */
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        return height(root) != -1;
    }
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = height(root.left);
        if(left < 0){
            return -1;
        }
        int right = height(root.right);
        if(right < 0){
            return -1;
        }
        if(Math.abs(left-right) <= 1){
            return Math.max(left,right) + 1;
        }
        return -1;
    }

    /*
    通过先序遍历遍的str构建二叉树，用中序遍历输出
    */
    /*
    class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val){
        this.val = val;
    }
}

public class Main {
    public static int i = 0;
    //将先序遍历的字符串转换成二叉树
    public static TreeNode toBinaryTree(String str){
        //中 左  右
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = toBinaryTree(str);
            root.right = toBinaryTree(str);
        }else{
            i++;
        }
        return root;
    }

    public static void inorder (TreeNode root){
        // 左 中 右
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.next();
            TreeNode root = toBinaryTree(str);
            inorder(root);
        }
    }
}
     */

    /**
     * 前序遍历非递归遍历
     * @param root 根
     */
    public void preOrderNode(TreeNode root){
        if(root == null) return ;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                System.out.print(cur.val+" ");
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        System.out.println();
    }

    /**
     * 二叉树中序非递归遍历
     * @param root 根
     */
    public void inOrderNot(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        //左 中 右
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //左边走到底了 出栈 并且打印
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
        System.out.println();
    }

    /**
     * 二叉树后序非递归遍历
     * @param root 根
     */
    public void postOrderNot(TreeNode root){
        if(root == null) return ;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || prev == top.right){
                stack.pop();
                System.out.print(top.val+" ");
                prev = top;
            }else{
                cur = top.right;
            }
        }
    }

    /**
     * 二叉树的层序遍历 -- 直接打印
     * @param root 根
     */
    public void levelOrder(TreeNode root){
        if(root == null) return ;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
            //出栈
        }
        System.out.println();
    }

    /**
     * 二叉树层序遍历 -- 放入List集合里面（正序）
     * @param root 根
     * @return 集合
     */
/*    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        //创建队列来实现
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> listChild = new ArrayList<>();
            while(size>0){
                TreeNode top = queue.poll();
                if(top.left != null){
                    queue.offer(top.left);
                }
                if(top.right != null){
                    queue.offer(top.right);
                }
                listChild.add(top.val);
                size--;
            }
            list.add(listChild);
        }
        return list;
    }*/

    /**
     * 二叉树层序遍历 -- 放入List集合里面（倒序）
     * @param root 根
     * @return 集合
     */
/*    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> listChild = new ArrayList<>();
            int size = queue.size();
            while(size != 0){
                TreeNode top = queue.poll();
                listChild.add(top.val);
                if(top.left != null){
                    queue.offer(top.left);
                }
                if(top.right != null){
                    queue.offer(top.right);
                }
                size--;
            }
            list.add(0,listChild);
        }
        return list;
    }*/

    /**
     * 寻找二叉树里面的公共祖先 -- 递归
     * @param root 根
     * @param p 节点1
     * @param q 节点2
     * @return 公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == q || root == p){
            return root;
        }
        TreeNode rootLeft = lowestCommonAncestor(root.left,p,q);
        TreeNode rootRight = lowestCommonAncestor(root.right,p,q);
        if(rootLeft != null && rootRight !=null){
            return root;
        }
        if(rootLeft != null){
            return rootLeft;
        }
        else{
            return rootRight;
        }
    }

    /**
     * 寻找二叉树里面的公共祖先 -- 非递归
     * @param root 根
     * @param p 节点1
     * @param q 节点2
     * @return 公共祖先
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        find(stackP,root,p);
        find(stackQ,root,q);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ - sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }
        }
        while(!stackP.isEmpty()){
            if(stackP.peek() != stackQ.peek()){
                stackQ.pop();
                stackP.pop();
            }else{
                return stackP.peek();
            }
        }
        return null;

    }
    public boolean find(Stack<TreeNode> stack,TreeNode root,TreeNode val){
        if(root == null) return false;
        stack.push(root);
        if(root == val){
            return true;
        }
        boolean left = find(stack,root.left,val);
        if(left){
            return true;
        }
        boolean right = find(stack,root.right,val);
        if(right){
            return true;
        }
        stack.pop();
        return false;

    }

    /**
     * 根据 前序(中 左 右) 中序(左 中 右) 创建二叉树
     */
    static class Solution {
        public int preIndex;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild(preorder,inorder,0,inorder.length-1);
        }
        private TreeNode buildTreeChild(int[] preorder, int[] inorder,int begin,int end){
            //通过遍历前序确定root  再根据begin和end确定左右子树
            if(begin > end){
                return null;
            }
            TreeNode root = new TreeNode(preorder[preIndex]);
            //在inorder里面找到root.val的下标
            int rootIndex = findIndex(inorder,root.val,begin,end);
            preIndex++;
            root.left = buildTreeChild(preorder,inorder,begin,rootIndex-1);
            root.right = buildTreeChild(preorder,inorder,rootIndex+1,end);
            return root;
        }
        private int findIndex(int[] inorder,int x,int begin,int end){
            for(int i = begin;i<= end;i++){
                if(inorder[i] == x){
                    return i;
                }
            }
            return -1;
        }
    }


    /**
     * 根据 后序(左 右 中) 中序(左 中 右) 创建二叉树
     */
    /*
    class Solution {
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,postIndex);
    }
    public TreeNode buildTreeChild(int[] inorder,int[] postorder,int begin,int end){
        if(begin > end){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int inRootIndex = findRootIndex(inorder,begin,end,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder,postorder,inRootIndex+1,end);
        root.left = buildTreeChild(inorder,postorder,begin,inRootIndex-1);
        return root;
    }
    public int findRootIndex(int[] inorder,int begin,int end,int x){
        for(int i = begin;i<=end;i++){
            if(inorder[i] == x){
                return i;
            }
        }
        return -1;
    }
}
     */

    //根据二叉树 创建字符串
/*    class Solution {
        public String tree2str(TreeNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            tree2strChild(root,stringBuilder);
            return stringBuilder.toString();
        }
        private void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
            if(root == null) return ;
            stringBuilder.append(root.val);//1
            if(root.left != null) {
                stringBuilder.append("(");
                tree2strChild(root.left,stringBuilder);
                stringBuilder.append(")");
            }else {
                //左边为空  右边也为空
                if(root.right == null) {
                    return;
                }else {
                    stringBuilder.append("()");
                }
            }
            //处理root右树的情况
            if(root.right == null) {
                return;
            }else {
                stringBuilder.append("(");
                tree2strChild(root.right,stringBuilder);
                stringBuilder.append(")");
            }
        }
    }*/
}
